
Working with metric graphs
David Bolin, Alexandre B. Simas, and Jonas Wallin
Created: 2022-11-23. Last modified: 2024-10-21.
Source:vignettes/metric_graph.Rmd
metric_graph.RmdIntroduction
Networks such as street or river networks are examples of metric graphs. A compact metric graph consists of a set of finitely many vertices and a finite set of edges connecting the vertices. Each edge is a curve of finite length that connects two vertices. These curves are parameterized by arc length and a location is a position on an edge, and can thus be represented as a touple where . Compared to regular graphs, where one typically defines functions on the vertices, we are for metric graphs interested in function that are defined on both the vertices and the edges.
In this vignette we will introduce the metric_graph
class of the MetricGraph package. This class provides a
user friendly representation of metric graphs, and we will show how to
use the class to construct and visualize metric graphs, add data to
them, and work with functions defined on the graphs.
For details about Gaussian processes and inference on metric graphs, we refer to the Vignettes
Constructing metric graphs
Basic constructions and properties
A metric graph can be constructed in two ways. The first is to
specify all edges in the graph as a list object, where each
entry is a matrix. To illustrate this, we first construct the following
edges
edge1 <- rbind(c(0,0),c(1,0))
edge2 <- rbind(c(0,0),c(0,1))
edge3 <- rbind(c(0,1),c(-1,1))
theta <- seq(from=pi,to=3*pi/2,length.out = 50)
edge4 <- cbind(sin(theta),1+ cos(theta))
edges = list(edge1, edge2, edge3, edge4)We can now create the graph based on the edges object as
follows
graph <- metric_graph$new(edges = edges)
graph$plot()
The plot function that was used to create the plot above has various
parameters to set the sizes and colors of the vertices and edges, and it
has a plotly argument to visualize the graph in 3D. For
this to work, the plotly library must be installed.
graph$plot(plotly = TRUE, vertex_size = 5, vertex_color = "blue",
edge_color = "red", edge_width = 2)## Warning: The `plotly` argument of `plot()` is deprecated as of MetricGraph 1.3.0.9000.
## ℹ Please use the `type` argument instead.
## ℹ The argument `plotly` was deprecated in favor of the argument `type`.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.
It is also important to know that the 2d version of the
plot() method returns a ggplot2 object and can
be modified as such. For instance:
p <- graph$plot()
p + ggplot2::labs(title = "Metric graph",
x = "long", y = "lat")
Similarly, the 3d version of the plot()
method returns a plotly object that can also be modified.
For instance:
p <- graph$plot(plotly = TRUE)
p <- plotly::layout(p, title = "Metric graph",
scene = list(xaxis=
list(title = "Long"),yaxis=list(title = "Lat")))
pWe can now obtain various properties of the graph: The vertex matrix, which specifies the Euclidian coordinates of the vertices is
graph$V## X Y
## [1,] 0 0
## [2,] 1 0
## [3,] 0 1
## [4,] -1 1
and the edge matrix that specified the edges of the graph (i.e., which vertices that are connected by edges) is
graph$E## [,1] [,2]
## [1,] 1 2
## [2,] 1 3
## [3,] 3 4
## [4,] 1 4
To obtain the geodesic (shortest path) distance between the vertices,
we can use the function compute_geodist:
graph$compute_geodist()
graph$geo_dist## $.vertices
## [,1] [,2] [,3] [,4]
## [1,] 0.000000 1.000000 1 1.570729
## [2,] 1.000000 0.000000 2 2.570729
## [3,] 1.000000 2.000000 0 1.000000
## [4,] 1.570729 2.570729 1 0.000000
The second option it to construct the graph using two matrices
V and E that specify the locations (in
Euclidean space) of the vertices and the edges. In this case, it is
assumed that the graph only has straight edges:
V <- rbind(c(0, 0), c(1, 0), c(0, 1), c(-1, 1))
E <- rbind(c(1, 2), c(1, 3), c(3, 4), c(4, 1))
graph2 <- metric_graph$new(V = V, E = E)## Starting graph creation...
## LongLat is set to FALSE
## Setting up edges
## Merging close vertices
## Total construction time: 0.19 secs
graph2$plot()
A third option is to create a graph from a SpatialLines
object:
library(sp)
line1 <- Line(rbind(c(0,0),c(1,0)))
line2 <- Line(rbind(c(0,0),c(0,1)))
line3 <- Line(rbind(c(0,1),c(-1,1)))
theta <- seq(from=pi,to=3*pi/2,length.out = 50)
line4 <- Line(cbind(sin(theta),1+ cos(theta)))
Lines = sp::SpatialLines(list(Lines(list(line1),ID="1"),
Lines(list(line2),ID="2"),
Lines(list(line3),ID="3"),
Lines(list(line4),ID="4")))
graph <- metric_graph$new(edges = Lines)
graph$plot()
A final option is to create from a MULTILINESTRING
object:
library(sf)
line1 <- st_linestring(rbind(c(0,0),c(1,0)))
line2 <- st_linestring(rbind(c(0,0),c(0,1)))
line3 <- st_linestring(rbind(c(0,1),c(-1,1)))
theta <- seq(from=pi,to=3*pi/2,length.out = 50)
line4 <- st_linestring(cbind(sin(theta),1+ cos(theta)))
multilinestring = st_multilinestring(list(line1, line2, line3, line4))
graph <- metric_graph$new(edges = multilinestring)
graph$plot()
Tolerances for merging vertices and edges
The constructor of the graph has one argument,
perform_merges and an additional argument
tolerance which is used for connecting edges that are close
in Euclidean space. Specifically, the tolerance argument is
given as a list with three elements:
-
vertex_vertexvertices that are closer than this number are merged (the default value is1e-7) -
vertex_edgeif a vertex at the end of one edge is closer than this number to another edge, this vertex is connected to that edge (the default value is1e-7) -
edge_edgeif two edges at some point are closer than this number, a new vertex is added at that point and the two edges are connected (the default value is0which means that the option is not used)
These options are often needed when constructing graphs based on real
data, for example from OpenStreetMap as we will see later. To illustrate
these options, suppose that we want to construct a graph from the
following three edges. We will set perform_merges to
TRUE, to show how they are merged with the default choice
of tolerances.
edge1 <- rbind(c(0,0),c(1,0))
edge2 <- rbind(c(0,0.03),c(0,0.75))
edge3 <- rbind(c(-1,1),c(0.5,0.03))
edge4 <- rbind(c(0,0.75), c(0,1))
edge5 <- rbind(c(-1,0), c(-1, 0.9995))
edges = list(edge1, edge2, edge3, edge4, edge5)
graph3 <- metric_graph$new(edges = edges, perform_merges = TRUE)
graph3$plot(degree = TRUE)
print(graph3$nV)## [1] 8

We added the option degree=TRUE to the plot here to
visualize the degrees of each vertex. As expected, one sees that all
vertices have degree 1, and none of the three edges are connected. If
these are streets in a street network, one might suspect that the two
vertices at
and
really should be the same vertex so that the two edges are connected.
This can be adjusted by increasing the vertex_vertex
tolerance:
graph3 <- metric_graph$new(edges = edges, perform_merges = TRUE,
tolerance = list(vertex_vertex = 0.05))
graph3$plot(degree = TRUE)
One might also want to add the vertex at
as a vertex on the first edge, so that the two edges there are
connected. This can be done by adjusting the vertex_edge
tolerance:
graph3 <- metric_graph$new(edges = edges, perform_merges = TRUE,
tolerance = list(vertex_vertex = 0.05,
vertex_edge = 0.1))
graph3$plot(degree = TRUE)
We can see that the vertex at
was indeed connected with the edge from
to
and that vertex now has degree 3 since it is connected with three edges.
One can also note that the edges object that was used to
create the graph is modified internally in the metric_graph
object so that the connections are visualized correctly in the sense
that all edges are actually shown as connected edges.
Finally, to add a vertex at the intersection between
edge2 and edge3 we can adjust the
edge_edge tolerance:
graph3 <- metric_graph$new(edges = edges, perform_merges = TRUE,
tolerance = list(vertex_vertex = 0.2,
vertex_edge = 0.1,
edge_edge = 0.001))
graph3$plot(degree = TRUE)
Now, the structure of the metric graph does not change if we add or
remove vertices of degree 2. Because of this,one might want to remove
vertices of degree 2 since this can reduce computational costs. This can
be done by setting the remove_deg2 argument while creating
the graph:
graph3 <- metric_graph$new(edges = edges, perform_merges = TRUE,
tolerance = list(vertex_vertex = 0.2,
vertex_edge = 0.1,
edge_edge = 0.001),
remove_deg2 = TRUE)
graph3$plot(degree = TRUE)
Observe that one vertex of degree 2 was not removed. This is due to
the fact that if we consider the direction, this vertex has directions
incompatible for removal. We can see this by setting the argument
direction=TRUE in the plot() method:
graph3$plot(direction = TRUE)
We can also avoid performing these merges by setting using the
default constructor (which is equivalent to set the
perform_merges argument to FALSE):
graph4 <- metric_graph$new(edges = edges)
graph4$plot(degree = TRUE)
Observe that the two vertices around the point
were merged. This is because there is an additional step to merge close
vertices that is performed even with perform_merges set to
FALSE. To also skip this merge, we can also set
merge_close_vertices to FALSE:
graph4 <- metric_graph$new(edges = edges, merge_close_vertices=FALSE)
graph4$plot(degree = TRUE)
We can see now that the two vertices around the point were not merged.
Edge lengths
Whenever we create a metric graph, the edge lengths will be automatically computed by obtaining the lengths of the edges. However, sometimes one might want to provide manual edge lengths.
Let us consider the following example:
library(sp)
line1 <- Line(rbind(c(0,0),c(1,0)))
line2 <- Line(rbind(c(0,0),c(0,1)))
line3 <- Line(rbind(c(0,1),c(-1,1)))
theta <- seq(from=pi,to=3*pi/2,length.out = 25)
line4 <- Line(cbind(sin(theta),1+ cos(theta)))
Lines = sp::SpatialLines(list(Lines(list(line1),ID="1"),
Lines(list(line2),ID="2"),
Lines(list(line3),ID="3"),
Lines(list(line4),ID="4")))
graph <- metric_graph$new(edges = Lines)
graph$plot()
We can obtain the edge lenghts by using the
get_edge_lengths() method:
graph$get_edge_lengths()## [1] 1.000000 1.000000 1.000000 1.570516
Observer that we know that the actual length of edge 4 is , which is not quite right (observe that edge 4 is an approximation of a quarter of a circle by a polygon with 25 points):
pi/2 - graph$get_edge_lengths()[4]## [1] 0.0002803513
We can provide the actual edge lengths, by using the
set_manual_edge_lengths() method:
graph$set_manual_edge_lengths(c(1,1,1,pi/2))
graph$get_edge_lengths()## [1] 1.000000 1.000000 1.000000 1.570796
We can also manually provide the edge lengths when creating the metric graph:
graph <- metric_graph$new(edges = Lines, manual_edge_lengths = c(1,1,1,pi/2))
graph$get_edge_lengths() ## [1] 1.000000 1.000000 1.000000 1.570796
However, it is important to note that if one passes the
manual_edge_lengths when creating the graph, it will automatically set
perform_merges to FALSE, as there is no
consistent way to obtain the edge lengths after the merges from the
manual edge lengths. Nevertheless, merge_close_vertices can
be set to TRUE.
Characteristics of the graph
A brief summary of the main characteristics of the graph can be
obtained by the compute_characteristics() method:
graph3$compute_characteristics()We can, then, view those characteristics by simply printing the
metric_graph object:
graph3## A metric graph with 6 vertices and 6 edges.
##
## Vertices:
## Degree 1: 3; Degree 2: 1; Degree 3: 1; Degree 4: 1;
## With incompatible directions: 1
##
## Edges:
## Lengths:
## Min: 0.3533333 ; Max: 2.190873 ; Total: 4.788107
## Weights:
## Min: 1 ; Max: 1
## That are circles: 0
##
## Graph units:
## Vertices unit: None ; Lengths unit: None
##
## Longitude and Latitude coordinates: FALSE
##
## Some characteristics of the graph:
## Connected: TRUE
## Has loops: FALSE
## Has multiple edges: FALSE
## Is a tree: FALSE
## Distance consistent: unknown
## To check if the graph satisfies the distance consistency, run the `check_distance_consistency()` method.
## Has Euclidean edges: unknown
## To check if the graph has Euclidean edges, run the `check_euclidean()` method.
Observe that we do not know that the graph has Euclidean edges. We
can check by using the check_euclidean() method:
graph3$check_euclidean()Let us view the characteristics again:
graph3## A metric graph with 6 vertices and 6 edges.
##
## Vertices:
## Degree 1: 3; Degree 2: 1; Degree 3: 1; Degree 4: 1;
## With incompatible directions: 1
##
## Edges:
## Lengths:
## Min: 0.3533333 ; Max: 2.190873 ; Total: 4.788107
## Weights:
## Min: 1 ; Max: 1
## That are circles: 0
##
## Graph units:
## Vertices unit: None ; Lengths unit: None
##
## Longitude and Latitude coordinates: FALSE
##
## Some characteristics of the graph:
## Connected: TRUE
## Has loops: FALSE
## Has multiple edges: FALSE
## Is a tree: FALSE
## Distance consistent: TRUE
## Has Euclidean edges: TRUE
It can happen that we have that the graph does not have Euclidean
edges without the need to check the distance consistency. However, if
one wants to check if the graph satisfies the distance consistency
assumption, one can run the check_distance_consistency()
function:
graph3$check_distance_consistency()Further, the individual characteristics can be accessed (after
running the compute_characteristics() method) through the
characteristics component of the graph object:
graph3$characteristics## $has_loops
## [1] FALSE
##
## $connected
## [1] TRUE
##
## $has_multiple_edges
## [1] FALSE
##
## $is_tree
## [1] FALSE
##
## $distance_consistency
## [1] TRUE
##
## $euclidean
## [1] TRUE
Summaries of metric graphs
We can also obtain a summary of the informations contained on a
metric graph object by using the summary() method. Let us
obtain a summary of informations of graph3:
summary(graph3)## A metric graph object with:
##
## Vertices:
## Total: 6
## Degree 1: 3; Degree 2: 1; Degree 3: 1; Degree 4: 1;
## With incompatible directions: 1
##
## Edges:
## Total: 6
## Lengths:
## Min: 0.3533333 ; Max: 2.190873 ; Total: 4.788107
## Weights:
## Min: 1 ; Max: 1
## That are circles: 0
##
## Graph units:
## Vertices unit: None ; Lengths unit: None
##
## Longitude and Latitude coordinates: FALSE
##
## Some characteristics of the graph:
## Connected: TRUE
## Has loops: FALSE
## Has multiple edges: FALSE
## Is a tree: FALSE
## Distance consistent: TRUE
## Has Euclidean edges: TRUE
##
## Computed quantities inside the graph:
## Laplacian: FALSE ; Geodesic distances: TRUE
## Resistance distances: FALSE ; Finite element matrices: FALSE
##
## Mesh: The graph has no mesh!
##
## Data: The graph has no data!
##
## Tolerances:
## vertex-vertex: 0.2
## vertex-edge: 0.1
## edge-edge: 0.001
Observe that there are some quantities that were not computed on the
summary. We can see how to compute them by setting the argument
messages to TRUE:
summary(graph3, messages = TRUE)## A metric graph object with:
##
## Vertices:
## Total: 6
## Degree 1: 3; Degree 2: 1; Degree 3: 1; Degree 4: 1;
## With incompatible directions: 1
##
## Edges:
## Total: 6
## Lengths:
## Min: 0.3533333 ; Max: 2.190873 ; Total: 4.788107
## Weights:
## Min: 1 ; Max: 1
## That are circles: 0
##
## Graph units:
## Vertices unit: None ; Lengths unit: None
##
## Longitude and Latitude coordinates: FALSE
##
## Some characteristics of the graph:
## Connected: TRUE
## Has loops: FALSE
## Has multiple edges: FALSE
## Is a tree: FALSE
## Distance consistent: TRUE
## Has Euclidean edges: TRUE
##
## Computed quantities inside the graph:
## Laplacian: FALSE ; Geodesic distances: TRUE
## To compute the Laplacian, run the 'compute_laplacian()' method.
## Resistance distances: FALSE ; Finite element matrices: FALSE
## To compute the resistance distances, run the 'compute_resdist()' method.
## To compute the finite element matrices, run the 'compute_fem()' method.
##
## Mesh: The graph has no mesh!
## To build the mesh, run the 'build_mesh()' method.
##
## Data: The graph has no data!
## To add observations, use the 'add_observations()' method.
##
## Tolerances:
## vertex-vertex: 0.2
## vertex-edge: 0.1
## edge-edge: 0.001
Finally, the summary() can also be accessed from the
metric graph object:
graph3$summary()## A metric graph object with:
##
## Vertices:
## Total: 6
## Degree 1: 3; Degree 2: 1; Degree 3: 1; Degree 4: 1;
## With incompatible directions: 1
##
## Edges:
## Total: 6
## Lengths:
## Min: 0.3533333 ; Max: 2.190873 ; Total: 4.788107
## Weights:
## Min: 1 ; Max: 1
## That are circles: 0
##
## Graph units:
## Vertices unit: None ; Lengths unit: None
##
## Longitude and Latitude coordinates: FALSE
##
## Some characteristics of the graph:
## Connected: TRUE
## Has loops: FALSE
## Has multiple edges: FALSE
## Is a tree: FALSE
## Distance consistent: TRUE
## Has Euclidean edges: TRUE
##
## Computed quantities inside the graph:
## Laplacian: FALSE ; Geodesic distances: TRUE
## Resistance distances: FALSE ; Finite element matrices: FALSE
##
## Mesh: The graph has no mesh!
##
## Data: The graph has no data!
##
## Tolerances:
## vertex-vertex: 0.2
## vertex-edge: 0.1
## edge-edge: 0.001
Vertices and edges
The metric graph object has the edges and
vertices elements in its list. We can get a quick summary
from them by calling these elements:
graph3$vertices## Vertices of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Summary:
## x y Degree Indegree Outdegree Problematic
## 1 0.0 0.0000000 2 0 2 TRUE
## 2 1.0 0.0000000 1 1 0 FALSE
## 3 0.5 0.0300000 3 2 1 FALSE
## 4 0.0 1.0000000 1 1 0 FALSE
## 5 -1.0 0.0000000 1 0 1 FALSE
## 6 0.0 0.3533333 4 2 2 FALSE
and
graph3$edges## [[1]]
## Edge 1 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Coordinates of the vertices of the edge:
## x y
## 0.0 0.00
## 0.5 0.03
##
## Coordinates of the edge:
## x y
## 0.0 0.00
## 0.5 0.03
## Relative positions of the coordinates on the graph edges were not computed.
## To compute them, run the `compute_PtE_edges()` method.
##
## Total number of coordinates: 2
## Edge length: 0.5008992
## Weight: 1
## Kirchhoff weight: 1
##
## Directional weight: 1
##
##
## [[2]]
## Edge 2 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Coordinates of the vertices of the edge:
## x y
## 0 0.0000000
## 0 0.3533333
##
## Coordinates of the edge:
## x y
## 0 0.0000000
## 0 0.3533333
## Relative positions of the coordinates on the graph edges were not computed.
## To compute them, run the `compute_PtE_edges()` method.
##
## Total number of coordinates: 2
## Edge length: 0.3533333
## Weight: 1
## Kirchhoff weight: 1
##
## Directional weight: 1
##
##
## [[3]]
## Edge 3 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Coordinates of the vertices of the edge:
## x y
## -1 0.0000000
## 0 0.3533333
##
## Coordinates of the edge:
## x y
## -1 0.0000000
## -1 1.0000000
## -1 1.0000000
## 0 0.3533333
## Relative positions of the coordinates on the graph edges were not computed.
## To compute them, run the `compute_PtE_edges()` method.
##
## Total number of coordinates: 4
## Edge length: 2.190873
## Weight: 1
## Kirchhoff weight: 1
##
## Directional weight: 1
##
##
## [[4]]
## Edge 4 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Coordinates of the vertices of the edge:
## x y
## 0 0.3533333
## 0 1.0000000
##
## Coordinates of the edge:
## x y
## 0 0.3533333
## 0 0.7500000
## 0 0.7500000
## 0 1.0000000
## Relative positions of the coordinates on the graph edges were not computed.
## To compute them, run the `compute_PtE_edges()` method.
##
## Total number of coordinates: 4
## Edge length: 0.6466667
## Weight: 1
## Kirchhoff weight: 1
##
## Directional weight: 1
##
##
## [[5]]
## Edge 5 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Coordinates of the vertices of the edge:
## x y
## 0.0 0.3533333
## 0.5 0.0300000
##
## Coordinates of the edge:
## x y
## 0.0 0.3533333
## 0.5 0.0300000
## Relative positions of the coordinates on the graph edges were not computed.
## To compute them, run the `compute_PtE_edges()` method.
##
## Total number of coordinates: 2
## Edge length: 0.5954363
## Weight: 1
## Kirchhoff weight: 1
##
## Directional weight: 1
##
##
## [[6]]
## Edge 6 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Coordinates of the vertices of the edge:
## x y
## 0.5 0.03
## 1.0 0.00
##
## Coordinates of the edge:
## x y
## 0.5 0.03
## 1.0 0.00
## Relative positions of the coordinates on the graph edges were not computed.
## To compute them, run the `compute_PtE_edges()` method.
##
## Total number of coordinates: 2
## Edge length: 0.5008992
## Weight: 1
## Kirchhoff weight: 1
##
## Directional weight: 1
We can also look at individual edges and vertices. For example, let us look at vertice number 2:
graph3$vertices[[2]]## Vertex 2 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Summary:
## x y Degree Indegree Outdegree Problematic
## 1 0 1 1 0 FALSE
Similarly, let us look at edge number 4:
graph3$edges[[4]]## Edge 4 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Coordinates of the vertices of the edge:
## x y
## 0 0.3533333
## 0 1.0000000
##
## Coordinates of the edge:
## x y
## 0 0.3533333
## 0 0.7500000
## 0 0.7500000
## 0 1.0000000
## Relative positions of the coordinates on the graph edges were not computed.
## To compute them, run the `compute_PtE_edges()` method.
##
## Total number of coordinates: 4
## Edge length: 0.6466667
## Weight: 1
## Kirchhoff weight: 1
##
## Directional weight: 1
We have a message informing us that the relative positions of the
edges were not computed. They are used to produce better plots when
using the plot_function() method, see the section
“Improving the plot obtained by plot_function” below. To
compute the relative positions, we run the
compute_PtE_edges() method:
graph3$compute_PtE_edges()Now, we take a look at edge number 4 again:
graph3$edges[[4]]## Edge 4 of the metric graph
##
## Longitude and Latitude coordinates: FALSE
##
## Coordinates of the vertices of the edge:
## x y
## 0 0.3533333
## 0 1.0000000
##
## Coordinates of the edge:
## x y
## 0 0.3533333
## 0 0.7500000
## 0 0.7500000
## 0 1.0000000
##
## Relative positions of the edge:
## Edge number Distance on edge
## 2 1.0000000
## 4 0.6134021
## 4 0.6134021
## 4 1.0000000
##
## Total number of coordinates: 4
## Edge length: 0.6466667
## Weight: 1
## Kirchhoff weight: 1
##
## Directional weight: 1
Understanding coordinates on graphs
The locations of the vertices are specified in Euclidean coordinates.
However, when specifying a position on the graph, it is not practical to
work with Euclidean coordinates since not all locations in Euclidean
space are locations on the graph. It is instead better to specify a
location on the graph by the touple
,
where
denotes the number of the edge and
is the location on the edge. The location
can either be specified as the distance from the start of the edge (and
then takes values between 0 and the length of the edge) or as the
normalized distance from the start of the edge (and then takes values
between 0 and 1). The function coordinates can be used to
convert between coordinates in Euclidean space and locations on the
graph. For example the location at distance 0.2 from the start of the
second edge is:
## [,1] [,2]
## [1,] 0 0.2
In this case, since the edge has length 1, the location of the point at normalized distance 0.2 from the start of the edge is the same:
## [,1] [,2]
## [1,] 0 0.2
The function can also be used to find the closest location on the graph for a location in Euclidean space:
## [,1] [,2]
## [1,] 2 0.2
In this case, the normalized argument decides whether
the returned value should be given in normalized distance or not.
Methods for working with real data
To illustrate the useage of metric_graph on some real
data, we use the osmdata package to download data from
OpenStreetMap. In the following code, we extract highways in the city of
Copenhagen:
library(osmdata)
call <- opq(getbb("Copenhagen"))
call <- add_osm_feature(call, key = "highway",value=c("motorway", "primary",
"secondary"))
data_sp <- osmdata_sp(call)
graph5 <- metric_graph$new(SpatialLines(data_sp$osm_lines@lines))## Warning in initialize(...): There is at least one edge of length zero. Please,
## consider redefining the graph.
graph5$plot(vertex_size = 0)
There are a few things to note about data like this. The first is that the coordinates are given in Longitude and Latitude. Because of this, the edge lengths are by default given in degrees, which may result in very small numbers:
range(graph5$get_edge_lengths())## [1] 0.00000000 0.05630008
This may cause numerical instabilities when dealing with random
fields on the graph, and it also makes it difficult to interpret results
(unless one has a good intuition about distances in degrees). To avoid
such problems, it is better to set the longlat argument
when constructing the graph:
graph5 <- metric_graph$new(SpatialLines(data_sp$osm_lines@lines), longlat = TRUE)## Warning in initialize(...): There is at least one edge of length zero. Please,
## consider redefining the graph.
This tells the constructor that the coordinates are given in Longitude and Latitude and that distances should be calculated in km. So if we now look at the edge lengths, they are given in km:
range(graph5$get_edge_lengths())## [1] 0.00000000 0.05630008
Alternatively, and more conveniently, whenever the
SpatialLines object has a valid proj4string,
it will automatically use this proj4string to set the
correct coordinate reference system (CRS) in the metric graph. Above, we
ended up removing the proj4string when we created the
SpatialLines object from the resulting
osm_lines. Let us, instead, build the graph directly using
the osmdata_sp object:
graph5 <- metric_graph$new(data_sp)## Warning in initialize(...): There is at least one edge of length zero. Please,
## consider redefining the graph.
We can see now that graph5 automatically has the correct
CRS:
graph5## A metric graph with 1458 vertices and 1490 edges.
##
## Vertices:
## Degree 1: 48; Degree 2: 1310; Degree 3: 88; Degree 4: 12;
## With incompatible directions: 3
##
## Edges:
## Lengths:
## Min: 0 ; Max: 4.05379 ; Total: 326.2565
## Weights:
## Columns: osm_id name access:lanes alt_name bicycle bicycle:lane bicycle:left bridge bus bus:lanes busway:right change:lanes check_date:cycleway check_date:surface communication covered cutting:right cycleway cycleway:both cycleway:both:lane cycleway:left cycleway:left:lane cycleway:left:oneway cycleway:right cycleway:right:lane cycleway:right:width cycleway:track:width cycleway:width destination destination:int_ref:lanes destination:lanes destination:ref destination:ref:to destination:symbol fixme foot foot:left footway:left hazard highway horse int_ref lane_markings lanes lanes:backward lanes:forward layer lit mapillary maxheight maxheight:signed maxspeed maxspeed:advisory maxspeed:variable maxweight:signed minspeed:lanes motorcar name:etymology name:etymology:wikidata noname note official_ref old_name old_name:wikipedia oneway oneway:bicycle operator operator:en operator:type operator:wikidata operator:wikipedia parking:both parking:left parking:right parking:right:orientation placement placement:backward placement:end placement:forward placement:start ref shoulder shoulder:right sidewalk sidewalk:both:surface sidewalk:left sidewalk:left:surface sidewalk:right sidewalk:right:surface smoothness source source:bicycle source:lanes source:lanes:date source:maxspeed source:official_ref source:start_date start_date surface temporary:date_off temporary:date_on temporary:oneway:bicycle toll tunnel tunnel:alt_name:da tunnel:alt_name:sv tunnel:name tunnel:name:da tunnel:name:de tunnel:name:en tunnel:name:sv tunnel:official_name turn turn:bus:lanes turn:lanes turn:lanes:backward turn:lanes:both_ways turn:lanes:forward unsigned_ref vehicle wikidata wikipedia .weights
## That are circles: 1
##
## Graph units:
## Vertices unit: degree ; Lengths unit: km
##
## Longitude and Latitude coordinates: TRUE
## Which spatial package: sp
## CRS: +proj=longlat +ellps=WGS84 +datum=WGS84 +no_defs +towgs84=0,0,0
This also allows us to plot the graph interactively with the
underlying world map, if the data has a coordinate reference system, by
setting type = "mapview" in the plot()
method:
graph5$plot(vertex_size = 0, type = "mapview")## Loading required namespace: mapview